{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Length of the Longest Valid Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestValidSubstring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长合法子字符串的长度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>word</code>&nbsp;和一个字符串数组&nbsp;<code>forbidden</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果一个字符串不包含&nbsp;<code>forbidden</code>&nbsp;中的任何字符串，我们称这个字符串是&nbsp;<strong>合法</strong>&nbsp;的。</p>\n",
    "\n",
    "<p>请你返回字符串 <code>word</code>&nbsp;的一个 <strong>最长合法子字符串</strong>&nbsp;的长度。</p>\n",
    "\n",
    "<p><strong>子字符串</strong> 指的是一个字符串中一段连续的字符，它可以为空。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>word = \"cbaaaabc\", forbidden = [\"aaa\",\"cb\"]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>总共有 11 个合法子字符串：\"c\", \"b\", \"a\", \"ba\", \"aa\", \"bc\", \"baa\", \"aab\", \"ab\", \"abc\" 和 \"aabc\"。最长合法子字符串的长度为 4 。\n",
    "其他子字符串都要么包含 \"aaa\" ，要么包含 \"cb\" 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>word = \"leetcode\", forbidden = [\"de\",\"le\",\"e\"]\n",
    "<strong>输出：</strong>4\n",
    "<b>解释：</b>总共有 11 个合法子字符串：\"l\" ，\"t\" ，\"c\" ，\"o\" ，\"d\" ，\"tc\" ，\"co\" ，\"od\" ，\"tco\" ，\"cod\" 和 \"tcod\" 。最长合法子字符串的长度为 4 。\n",
    "所有其他子字符串都至少包含 \"de\" ，\"le\" 和 \"e\" 之一。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= word.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>word</code>&nbsp;只包含小写英文字母。</li>\n",
    "\t<li><code>1 &lt;= forbidden.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= forbidden[i].length &lt;= 10</code></li>\n",
    "\t<li><code>forbidden[i]</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [length-of-the-longest-valid-substring](https://leetcode.cn/problems/length-of-the-longest-valid-substring/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [length-of-the-longest-valid-substring](https://leetcode.cn/problems/length-of-the-longest-valid-substring/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"cbaaaabc\"\\n[\"aaa\",\"cb\"]', '\"leetcode\"\\n[\"de\",\"le\",\"e\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, s: str, forbidden: List[str]) -> int:\n",
    "        \n",
    "        trie = {}\n",
    "        \n",
    "        \n",
    "        for word in forbidden:\n",
    "            node = trie\n",
    "            for w in word:\n",
    "                node = node.setdefault(w, {})\n",
    "            node['*'] = word\n",
    "        \n",
    "        \n",
    "        n = len(s)\n",
    "        right = n\n",
    "        ans = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            node = trie\n",
    "            for j in range(i, min(i+10, right)):\n",
    "                if s[j] not in node:\n",
    "                    break\n",
    "                node = node[s[j]]\n",
    "                if '*' in node:\n",
    "                    right = j\n",
    "                    break\n",
    "            \n",
    "            ans = max(ans, right - i)\n",
    "        \n",
    "        return ans\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        helper = dict()\n",
    "\n",
    "        for f in forbidden:\n",
    "            last = f[-1]\n",
    "            if last not in helper:\n",
    "                helper[last] = defaultdict(set)\n",
    "            helper[last][len(f)].add(f)\n",
    "\n",
    "        n = len(word)\n",
    "        left, right = 0, 0\n",
    "\n",
    "        res = 0\n",
    "        cur = \"\"\n",
    "        while right < n:\n",
    "            cur += word[right]\n",
    "\n",
    "            min_dup = 20\n",
    "            if word[right] in helper:\n",
    "                h = helper[word[right]]\n",
    "                for l, all_set in h.items():\n",
    "                    if l > len(cur):\n",
    "                        continue\n",
    "                    now = cur[len(cur)-l:]\n",
    "                    if now in all_set:\n",
    "                        min_dup = min(min_dup, l)\n",
    "            if min_dup != 20:\n",
    "                #print(min_dup, cur)\n",
    "                left += right - left - min_dup + 2\n",
    "\n",
    "            #print(cur, left, right)\n",
    "            cur = word[left:right+1]\n",
    "            res = max(res, len(cur))\n",
    "            right += 1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        n = len(word)\n",
    "        ans = 0\n",
    "        arr = [set() for _ in range(11)]\n",
    "        for s in forbidden:\n",
    "            arr[len(s)].add(s)\n",
    "        \n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            for k in range(10):\n",
    "                if i - k < j: break\n",
    "                if word[i-k:i+1] in arr[k+1]:\n",
    "                    j = i - k + 1\n",
    "                    break\n",
    "            ans = max(ans, i - j + 1)\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution0:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)\n",
    "        left = 0\n",
    "        res = 0\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right, max(right - 10, left-1),-1):\n",
    "                if word[i:right+1] in forbidden:\n",
    "                    left = i + 1\n",
    "                    break\n",
    "            res = max(res, right - left + 1)\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)   #[left, right]\n",
    "                            #          [r-10\n",
    "                            # [r-10    \n",
    "        ans = left = 0\n",
    "        for right in range(len(word)):\n",
    "            # print('test_word:', word[left:right+1])\n",
    "            for i in range(right, max(right - 10, left - 1), -1):\n",
    "                if word[i: right + 1] in fb:\n",
    "                    print('     xx:', word[i: right + 1])\n",
    "                    left = i + 1  # 当子串右端点 >= right 时，合法子串一定不能包含 word[i]\n",
    "                    break\n",
    "            ans = max(ans, right - left + 1)\n",
    "            # print('     valid:', word[left: right + 1], ',len:', (right - left + 1))\n",
    "        return ans\n",
    "#             L\n",
    "# word = \"cbaaaabc\", forbidden = [\"aaa\",\"cb\"]\n",
    "#                R\n",
    "# test_word: c\n",
    "#      valid: c ,len: 1\n",
    "# test_word: cb\n",
    "#      xx: cb\n",
    "#      valid: b ,len: 1\n",
    "# test_word: ba\n",
    "#      valid: ba ,len: 2\n",
    "# test_word: baa  \n",
    "#      valid: baa ,len: 3\n",
    "# test_word: baaa \n",
    "#      xx: aaa\n",
    "#      valid: aa ,len: 2\n",
    "# test_word: aaa\n",
    "#      xx: aaa\n",
    "#      valid: aa ,len: 2  \n",
    "# test_word: aab\n",
    "#      valid: aab ,len: 3 \n",
    "# test_word: aabc\n",
    "#      valid: aabc ,len: 4 <<<<"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        st=set(forbidden)\n",
    "\n",
    "        n=len(word)\n",
    "        left=i=0\n",
    "        res=0\n",
    "        while i<n:            \n",
    "            for j in range(1,min(i-left+1,10)+1):\n",
    "                L=i-j+1\n",
    "                if word[L:i+1] in st:\n",
    "                    left=L+1\n",
    "                    break\n",
    "            \n",
    "            res=max(res,i-left+1)\n",
    "            i+=1\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        M = max(len(w) for w in forbidden)\n",
    "        fset = set(forbidden)\n",
    "        last_start = 0\n",
    "        ans = 0\n",
    "        for i in range(1, len(word) + 1):\n",
    "            for j in range(1, min(i - last_start, M) + 1):\n",
    "                if word[i - j: i] in fset:\n",
    "                    ans = max(ans, i - last_start - 1)\n",
    "                    last_start = i - j + 1\n",
    "                    break\n",
    "        ans = max(ans, len(word) - last_start)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fbs = set(forbidden)\n",
    "        ans = left = 0\n",
    "        for right, x in enumerate(word):\n",
    "            for i in range(right, max(left - 1, right - 10), -1):\n",
    "                if word[i : right + 1] in fbs:\n",
    "                    left = i + 1\n",
    "                    break\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)\n",
    "        left = 0\n",
    "        right = 0\n",
    "        ans = 0\n",
    "        while (left <= right < len(word)):\n",
    "            right += 1\n",
    "            flag = 0\n",
    "            left1 = max(right-10, left)\n",
    "            while(left1 < right):\n",
    "                m = word[left1:right]\n",
    "                while m in fb and left1 < right:\n",
    "                    left1 += 1\n",
    "                    m = word[left1:right]\n",
    "                    left = left1\n",
    "                left1 += 1\n",
    "                \n",
    "                \n",
    "            ans = max(ans, right-left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        t = set(forbidden)\n",
    "        lenth = 0\n",
    "        for s in t:\n",
    "            lenth = max(lenth,len(s))\n",
    "        left = 0\n",
    "        right = 0\n",
    "        ans = 0\n",
    "        def isvalid(l,r):\n",
    "            for mid in range(max(l,r-lenth),r):\n",
    "                if word[mid:r] in t:\n",
    "                    return False\n",
    "            return True\n",
    "        while left<len(word)-ans:\n",
    "            right = left+1\n",
    "            while right <= len(word) and isvalid(left,right):\n",
    "                ans = max(right-left,ans)\n",
    "                right += 1\n",
    "            left = max(left,right-lenth)\n",
    "\n",
    "            while left<right and word[left:right] not in t:\n",
    "                left += 1\n",
    "            left += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, s: str, forbidden: List[str]) -> int:\n",
    "        n = len(s)\n",
    "        f = set(forbidden)\n",
    "        m = max(len(i) for i in forbidden)\n",
    "        l = 0\n",
    "        res = 0\n",
    "        for r in range(n):\n",
    "            for d in range(m):\n",
    "                if r - d < l:\n",
    "                    break\n",
    "                if s[r - d:r + 1] in f:\n",
    "                    l = r - d + 1\n",
    "                    break\n",
    "            res = max(res, r - l + 1)\n",
    "        return res\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        n = len(word)\n",
    "        ans = 0\n",
    "        arr = [set() for _ in range(11)]\n",
    "        for s in forbidden:\n",
    "            arr[len(s)].add(s)\n",
    "        \n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            for k in range(10):\n",
    "                if i - k < j: break\n",
    "                if word[i-k:i+1] in arr[k+1]:\n",
    "                    j = i - k + 1\n",
    "                    break\n",
    "            ans = max(ans, i - j + 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)\n",
    "        ans = left = 0\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right, max(right - 10, left - 1), -1):\n",
    "                if word[i: right + 1] in fb:\n",
    "                    left = i + 1  # 当子串右端点 >= right 时，合法子串一定不能包含 word[i]\n",
    "                    break\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)  # 将禁止字符串列表转换为集合，以提高查找效率\n",
    "        res = 0  # 用于存储最长有效子串的长度\n",
    "        l = 0  # 滑动窗口的左边界\n",
    "\n",
    "        for r in range(len(word)):  # 滑动窗口的右边界从左到右遍历\n",
    "            for i in range(r, max(r - 10, l - 1), -1):  # 从右向左遍历窗口内的子串\n",
    "                if word[i:r + 1] in fb:  # 如果窗口内的子串在禁止字符串集合中\n",
    "                    l = i + 1  # 更新左边界，排除当前禁止字符串\n",
    "                    break  # 跳出内层循环，以继续遍历下一个子串\n",
    "\n",
    "            res = max(res, r - l + 1)  # 更新最长有效子串的长度\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        setF=set(forbidden)\n",
    "        res=left=0\n",
    "        for i in range (len(word)):\n",
    "            for j in range (max(left,i-9),i+1):\n",
    "                if word[j:i+1] in setF:\n",
    "                    left=j+1\n",
    "            res=max(res,i-left+1)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, s: str, forbidden: List[str]) -> int:\n",
    "        n = len(s)\n",
    "        mx, mn = 0, 10\n",
    "        MOD = 10 ** 9 + 7\n",
    "        f = set()\n",
    "        for i in forbidden:\n",
    "            if len(i) > mx: mx = len(i)\n",
    "            if len(i) < mn: mn = len(i)\n",
    "            f.add(i)\n",
    "        l = res = 0\n",
    "        for r in range(n):\n",
    "            for d in range(mn - 1, mx):\n",
    "                if r - d < l:\n",
    "                    break\n",
    "                if s[r - d:r + 1] in f:\n",
    "                    l = r - d + 1\n",
    "                    break\n",
    "            res = max(res, r - l + 1)\n",
    "        return res\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)\n",
    "        ans = left = 0\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right, max(right - 10, left - 1), -1):\n",
    "                if word[i: right + 1] in fb:\n",
    "                    left = i + 1  # 当子串右端点 >= right 时，合法子串一定不能包含 word[i]\n",
    "                    break\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)\n",
    "        ans = left = 0\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right, max(right - 10, left - 1), -1):\n",
    "                if word[i: right + 1] in fb:\n",
    "                    left = i + 1  # 当子串右端点 >= right 时，合法子串一定不能包含 word[i]\n",
    "                    break\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/length-of-the-longest-valid-substring/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fbs = set(forbidden)\n",
    "        ans = left = 0\n",
    "        for right, x in enumerate(word):\n",
    "            for i in range(right, max(left - 1, right - 10), -1):\n",
    "                if word[i : right + 1] in fbs:\n",
    "                    left = i + 1\n",
    "                    break\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        n = len(word)\n",
    "        s = set(forbidden)\n",
    "        st = 0\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(9, -1, -1):\n",
    "                if i - j >= 0:\n",
    "                    if word[i - j:i+1] in s:\n",
    "                        st = max(st, i - j + 1)\n",
    "            res = max(res, i - st + 1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "      left = jie = 0\n",
    "      fd = set(forbidden)\n",
    "      for right in range(len(word)):\n",
    "        for i in range(right,max(right-10,left-1),-1):\n",
    "          if word[i:right+1] in fd:\n",
    "            left = i+1\n",
    "            break\n",
    "        jie = max(jie,right-left+1)\n",
    "      return jie \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        ans = left = 0\n",
    "        fb = set(forbidden)\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right, max(right-10, left-1), -1):\n",
    "                if word[i:right+1] in fb:\n",
    "                    left = 1 + i\n",
    "                    break\n",
    "            ans = max(ans, right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        f = set(forbidden)\n",
    "        for right in range(len(word)):\n",
    "            # 关键，forbidden只有10\n",
    "            for i in range(right, max(right - 10, left - 1), -1):\n",
    "                if word[i:right+1] in f:\n",
    "                    left = i + 1\n",
    "                    break\n",
    "            else:\n",
    "                ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        ans = left = 0\n",
    "        fb_set = set(forbidden)\n",
    "        for right in range(len(word)):\n",
    "            for j in range(right, max(-1, left - 1, right - 10), -1):\n",
    "                if word[j:right + 1] in fb_set:\n",
    "                    left = j + 1\n",
    "                    break\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)\n",
    "        ans = left = 0\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right, max(right-10, left-1), -1):\n",
    "                if word[i:right+1] in fb:\n",
    "                    left = i + 1\n",
    "                    break\n",
    "            ans = max(ans, right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)\n",
    "        mx = max(len(f) for f in forbidden)\n",
    "        mn = min(len(f) for f in forbidden)\n",
    "        ans = left = 0\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right-mn+1, max(right - mx, left - 1), -1):\n",
    "                if word[i: right + 1] in fb:\n",
    "                    left = i + 1  # 当子串右端点 >= right 时，合法子串一定不能包含 word[i]\n",
    "                    break\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/length-of-the-longest-valid-substring/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        n=len(word)\n",
    "        i,j=0,0\n",
    "        ans=0\n",
    "        d=set(forbidden)\n",
    "        def valid(i,j):\n",
    "            s=word[i:j+1]\n",
    "            #print(i,j,s)\n",
    "            lens=len(s)\n",
    "            for i in range(1,min(11,lens+1)):\n",
    "                if s[lens-i:] in d:\n",
    "                    return False\n",
    "            return True\n",
    "        while j<n:\n",
    "            while i<=j and not valid(i,j):\n",
    "                i+=1\n",
    "            #print(i,j)\n",
    "            ans=max(ans,j-i+1)\n",
    "            j+=1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)  # 把forbidden中的字符串放入一个哈希集合中\n",
    "        ans = left = 0  # 初始化结果和左指针\n",
    "        \n",
    "        for right in range(len(word)):\n",
    "            # 检查从 right 到 max(right - 10, left - 1) 这个范围内的子字符串\n",
    "            for i in range(right, max(right - 10, left - 1), -1):\n",
    "                if word[i:right + 1] in fb:\n",
    "                    left = i + 1  # 当子串的右端点 >= right 时，合法子串一定不能包含 word[i:right+1]\n",
    "                    break  # 跳出内部循环\n",
    "            \n",
    "            ans = max(ans, right - left + 1)  # 更新最长合法子字符串的长度\n",
    "            \n",
    "        return ans  # 返回结果\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        ma = set(forbidden)\n",
    "        n = len(word)\n",
    "        left, right = 0, 0 \n",
    "        ans = 0 \n",
    "        while right < n:\n",
    "            flag = 1 \n",
    "            for i in range(min(right - left+1, 10)):\n",
    "                tmp = word[right-i:right+1]\n",
    "                if tmp in ma:\n",
    "                    flag = 0\n",
    "                    left = right - i + 1\n",
    "                    break   \n",
    "            if flag:\n",
    "                ans = max(ans, right - left + 1)\n",
    "            right += 1\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Q4: https://www.bilibili.com/video/BV1DM4y1x7bR\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right, max(right - 10, left - 1), -1):\n",
    "                if word[i: right + 1] in fb:\n",
    "                    left = i + 1\n",
    "                    break\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)\n",
    "        ans = left = 0\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right, max(right - 10, left - 1), -1):\n",
    "                if word[i: right + 1] in fb:\n",
    "                    left = i + 1  # 当子串右端点 >= right 时，合法子串一定不能包含 word[i]\n",
    "                    break\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def longestValidSubstring(self, word, forbidden):\n",
    "        \"\"\"\n",
    "        :type word: str\n",
    "        :type forbidden: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maxcount=0\n",
    "        forbidden=set(forbidden)\n",
    "        left=0\n",
    "        while len(word)>0:\n",
    "            minlon=len(word)+1\n",
    "            for n in range(left,len(word)):\n",
    "                for i in range(1,11):\n",
    "                    if n+1-i>=left:\n",
    "                        s=word[n+1-i:n+1]\n",
    "                        if s in forbidden:\n",
    "                            minlon=min(minlon,i)\n",
    "                if minlon!=len(word)+1:\n",
    "                    maxcount=max(maxcount,n-left)\n",
    "                    left=n-minlon+2\n",
    "                    n=0\n",
    "                    break                 \n",
    "            if n==len(word)-1 or left>=len(word):\n",
    "                maxcount=max(maxcount,n-left+1)\n",
    "                break\n",
    "        return maxcount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)\n",
    "        ans = left = 0\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right, max(right - 10, left - 1), -1): \n",
    "                # 反向\n",
    "                # [left, right] 不会回到0 保证算法效率\n",
    "                # 因为forbidden[i].length in [1, 10]，所以要优化一下，否则超时\n",
    "                if word[i: right + 1] in fb:\n",
    "                    left = i + 1\n",
    "                    break\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb=set(forbidden)\n",
    "        left=0\n",
    "        ans=0\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right,right-10,-1):\n",
    "                if i<left:\n",
    "                    break\n",
    "                if word[i:right+1] in fb:\n",
    "                    left=i+1\n",
    "            ans=max(ans,right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)\n",
    "        left = 0\n",
    "        ans = 0\n",
    "\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right,max(right - 10,left - 1),-1):\n",
    "                if word[i: right + 1] in fb:\n",
    "                    left = i + 1\n",
    "                    break\n",
    "            ans = max(ans,right - left + 1)\n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        n = len(word)\n",
    "        fbSet = set(forbidden)\n",
    "        l = 0\n",
    "        res = 0\n",
    "\n",
    "        for r in range(n):\n",
    "            for i in range(r, max(r - 10, l - 1), -1):\n",
    "                if word[i: r + 1] in fbSet:\n",
    "                    l = i + 1\n",
    "                    break\n",
    "            res = max(res, r - l + 1)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)\n",
    "        ans = left = 0\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right, max(right - 10, left - 1), -1):\n",
    "                if word[i: right + 1] in fb:\n",
    "                    left = i + 1  # 当子串右端点 >= right 时，合法子串一定不能包含 word[i]\n",
    "                    break\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def longestValidSubstring(self, word, forbidden):\n",
    "        \"\"\"\n",
    "        :type word: str\n",
    "        :type forbidden: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maxcount=0\n",
    "        forbidden=set(forbidden)\n",
    "        left=0\n",
    "        while len(word)>0:\n",
    "            minlon=len(word)+1\n",
    "            for n in range(left,len(word)):\n",
    "                for i in range(1,11):\n",
    "                    if n+1-i>=left:\n",
    "                        s=word[n+1-i:n+1]\n",
    "                        if s in forbidden:\n",
    "                            minlon=min(minlon,i)\n",
    "                if minlon!=len(word)+1:\n",
    "                    maxcount=max(maxcount,n-left)\n",
    "                    left=n-minlon+2\n",
    "                    n=0\n",
    "                    break                 \n",
    "            if n==len(word)-1 or left>=len(word):\n",
    "                maxcount=max(maxcount,n-left+1)\n",
    "                break\n",
    "        return maxcount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        a=set(forbidden)\n",
    "        n=len(word)\n",
    "        left=0\n",
    "        ans=0\n",
    "        for right in range(n):\n",
    "            for j in range(right,max(right-10,left-1),-1):\n",
    "\n",
    "                if word[j:right+1] in a:\n",
    "                    left=j+1\n",
    "                    break\n",
    "            ans=max(ans,right-left+1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        ans = left = 0\n",
    "        fb_set = set(forbidden)\n",
    "        for right in range(len(word)):\n",
    "            for j in range(right, max(left - 1, right - 10), -1):\n",
    "                if word[j:right + 1] in fb_set:\n",
    "                    left = j + 1\n",
    "                    break\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb=set(forbidden)\n",
    "        ans=0\n",
    "        l=0\n",
    "        for r in range(len(word)):\n",
    "            for i in range(r,max(l-1,r-10),-1):\n",
    "                if word[i:r+1] in fb:\n",
    "                    l=i+1\n",
    "                    break\n",
    "            ans=max(ans,r-l+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        visited = set(forbidden)\n",
    "        lens =sorted(set(len(f) for f in forbidden))\n",
    "        n = len(word)\n",
    "        ans = 0\n",
    "        r = n\n",
    "\n",
    "        for l in range(n-1,-1,-1):\n",
    "            for length in lens:\n",
    "                if l + length > r:\n",
    "                    break\n",
    "                if word[l:l+length] in visited:\n",
    "                    r = l+length - 1\n",
    "                    break \n",
    "            ans = max(ans, r-l)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)\n",
    "        ans = left = 0\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right, max(right - 10, left - 1), -1):\n",
    "                if word[i: right + 1] in fb:\n",
    "                    left = i + 1  # 当子串右端点 >= right 时，合法子串一定不能包含 word[i]\n",
    "                    break\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        maxcount=0\n",
    "        forbidden=set(forbidden)\n",
    "        left=0\n",
    "        while len(word)>0:\n",
    "            minlon=len(word)+1\n",
    "            for n in range(left,len(word)):\n",
    "                for i in range(1,11):\n",
    "                    if n+1-i>=left:\n",
    "                        s=word[n+1-i:n+1]\n",
    "                        if s in forbidden:\n",
    "                            minlon=min(minlon,i)\n",
    "                if minlon!=len(word)+1:\n",
    "                    maxcount=max(maxcount,n-left)\n",
    "                    left=n-minlon+2\n",
    "                    n=0\n",
    "                    break                 \n",
    "            if n==len(word)-1 or left>=len(word):\n",
    "                maxcount=max(maxcount,n-left+1)\n",
    "                break\n",
    "        return maxcount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)\n",
    "        ans = 0 \n",
    "        left = 0\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right, max(left-1, right - 10), -1):\n",
    "                if word[i:right+1] in fb:\n",
    "                    left = i + 1\n",
    "                    break \n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)\n",
    "        ans = left = 0\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right, max(right - 10, left - 1), -1):\n",
    "                if word[i: right + 1] in fb:\n",
    "                    left = i + 1  # 当子串右端点 >= right 时，合法子串一定不能包含 word[i]\n",
    "                    break\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb_set = set(forbidden)\n",
    "        left = 0\n",
    "        res = 0\n",
    "        n = len(word)\n",
    "        for right in range(n):\n",
    "            for i in range(right, max(right-10, left-1), -1):\n",
    "                if word[i:right+1] in fb_set:\n",
    "                    left = i+1\n",
    "                    break\n",
    "            res = max(res, right-left+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        t = set(forbidden)\n",
    "        left = 0\n",
    "        right = 0\n",
    "        ans = 0\n",
    "        def isvalid(l,r):\n",
    "            for mid in range(max(l,r-10),r):\n",
    "                if word[mid:r] in t:\n",
    "                    return False\n",
    "            return True\n",
    "        while left<len(word)-ans:\n",
    "            right = left+1\n",
    "            while right <= len(word) and isvalid(left,right):\n",
    "                ans = max(right-left,ans)\n",
    "                right += 1\n",
    "\n",
    "            while left<right and word[left:right] not in t:\n",
    "                left += 1\n",
    "            left += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fb = set(forbidden)\n",
    "        left, ret, n = 0, 0, len(word)\n",
    "        for right in range(n):\n",
    "            for i in range(right, max(right-10, left-1), -1):\n",
    "                if word[i:right+1] in fb:\n",
    "                    left = i + 1\n",
    "                    break\n",
    "            ret = max(right-left+1, ret)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        left=0\n",
    "        ans=0\n",
    "        fb=set(forbidden)\n",
    "        for right in range(len(word)):\n",
    "            for i in range(right,max(right-10,left-1),-1):\n",
    "                if word[i:right+1] in fb:\n",
    "                    left=i+1\n",
    "                    break\n",
    "            ans=max(ans,right-left+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.finish = False\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        visited = set(forbidden)\n",
    "        lens =sorted(set(len(f) for f in forbidden))\n",
    "        n = len(word)\n",
    "        ans = 0\n",
    "        r = n\n",
    "\n",
    "        for l in range(n-1,-1,-1):\n",
    "            for length in lens:\n",
    "                if l + length > r:\n",
    "                    break\n",
    "                if word[l:l+length] in visited:\n",
    "                    r = l+length - 1\n",
    "                    break \n",
    "            ans = max(ans, r-l)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        f=set(forbidden)\n",
    "        l=0\n",
    "        n=len(word)\n",
    "        ans=0\n",
    "        for r in range(n):\n",
    "            for j in range(r,max(r-11,l-1),-1):\n",
    "                if word[j:r+1] in f:\n",
    "                    l=j+1\n",
    "                \n",
    "                    break\n",
    "                #print(l,r)\n",
    "            ans=max(ans,r-l+1)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        n = len(word)\n",
    "        s = set(forbidden)\n",
    "        # res = 0\n",
    "        # dp = [10 ** 5 + 1] * n\n",
    "        dp = list(range(n, 0, -1))\n",
    "        # dp[-1] = 1\n",
    "        # print(\"dp\", dp)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # print(\"i\", i)\n",
    "            for j in range(10):\n",
    "                if i + j < n and word[i: i + j + 1] in s:\n",
    "                    # print(\"i, j\", i, j)\n",
    "                    dp[i] = j\n",
    "                    break\n",
    "            for j in range(10):\n",
    "                if i + j < n:\n",
    "                    dp[i] = min(dp[i + j] + j, dp[i])\n",
    "            # print(\"med dp\", dp)\n",
    "        # print(\"after dp\", dp)\n",
    "        return max(dp)\n",
    "                \n",
    "                \n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, s: str, forbidden: List[str]) -> int:\n",
    "        n = len(s)\n",
    "        m = 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def Hashvalue(s):\n",
    "            n = len(s)\n",
    "            return sum(pow(ord(s[i]) - ord('a') + 4, n - i, MOD) for i in range(n)) % MOD\n",
    "        f = set()\n",
    "        for i in forbidden:\n",
    "            if len(i) > m: m = len(i)\n",
    "            f.add(Hashvalue(i))\n",
    "        l = 0\n",
    "        res = 0\n",
    "        for r in range(n):\n",
    "            v = 0\n",
    "            for d in range(m):\n",
    "                v = (v + pow(ord(s[r - d]) - ord('a') + 4, d + 1, MOD)) % MOD\n",
    "                if r - d < l:\n",
    "                    break\n",
    "                if v in f:\n",
    "                    l = r - d + 1\n",
    "                    break\n",
    "            res = max(res, r - l + 1)\n",
    "        return res\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        l,r,n,opt,ans=0,0,len(word),0,0\n",
    "        forbidden={i:1 for i in forbidden}\n",
    "        while(r<n):\n",
    "            for i in range(0,10):\n",
    "                if(forbidden.get(word[max(l,r-i):r+1],0)):\n",
    "                    ans=max(ans,r-l);l,r=r-i+1,r-i+1;opt=1;break\n",
    "            if(opt):opt=0;continue\n",
    "            r+=1\n",
    "        ans=max(ans,r-l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        j = 0 \n",
    "        n = len(word) \n",
    "        fset = set(forbidden)\n",
    "        ans = 0 \n",
    "        dp = [0] * n \n",
    "        pre = 0 \n",
    "        for i in range(n):\n",
    "            flag = 10\n",
    "            for j in range(i, max(i-9,i-pre)-1, -1):\n",
    "                if word[j:i+1] in fset:\n",
    "                    flag = i-j\n",
    "                    break \n",
    "            if flag == 10:\n",
    "                dp[i] = pre + 1\n",
    "                pre = dp[i]  \n",
    "            else:\n",
    "                dp[i] = flag \n",
    "                pre = dp[i] \n",
    "            ans = max(ans, dp[i]) \n",
    "        print(dp)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        j = 0 \n",
    "        n = len(word) \n",
    "        fset = set(forbidden)\n",
    "        ans = 0 \n",
    "        dp = [0] * n \n",
    "        pre = 0 \n",
    "        for i in range(n):\n",
    "            flag = 10\n",
    "            for j in range(i, max(i-10,i-pre)-1, -1):\n",
    "                if word[j:i+1] in fset:\n",
    "                    flag = i-j\n",
    "                    break \n",
    "            if flag == 10:\n",
    "                dp[i] = pre + 1\n",
    "                pre = dp[i]  \n",
    "            else:\n",
    "                dp[i] = flag \n",
    "                pre = dp[i] \n",
    "            ans = max(ans, dp[i]) \n",
    "        print(dp)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        dp=[-1]*len(word)\n",
    "        a=set(forbidden)\n",
    "        ans=0\n",
    "        for i in range(min(10,len(word))):\n",
    "            for j in range(i+1):\n",
    "                if word[i-j:i+1] in a:\n",
    "                    if i>0:\n",
    "                        dp[i]=min(j,dp[i-1]+1)\n",
    "                    else:\n",
    "                        dp[i]=0\n",
    "                    ans=max(ans,dp[i])\n",
    "                    break\n",
    "            if dp[i]==-1:\n",
    "                if i==0:\n",
    "                    dp[i]=1\n",
    "                else:\n",
    "                    dp[i]=dp[i-1]+1\n",
    "                ans=max(ans,dp[i])\n",
    "        if len(word)>10:\n",
    "            for i in range(10,len(word)):\n",
    "                for j in range(10):\n",
    "                    if word[i-j:i+1] in a:\n",
    "                        dp[i]=min(j,dp[i-1]+1)\n",
    "                        ans=max(ans,dp[i])\n",
    "                        break\n",
    "                if dp[i]==-1:\n",
    "                    dp[i]=dp[i-1]+1\n",
    "                    ans=max(ans,dp[i])\n",
    "        print(dp)\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        s = set()\n",
    "        for v in forbidden:\n",
    "            s.add(v[::-1])\n",
    "        n = len(word)\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        for r in range(n):\n",
    "            strs = ''\n",
    "            for i in range(1,11,1):\n",
    "                if r-i+1 < l:\n",
    "                    break\n",
    "                strs += word[r-i+1]\n",
    "                if strs in s:\n",
    "                    l = r-i+2\n",
    "                    break\n",
    "            ans = max(ans,r-l+1)\n",
    "        return ans\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush\n",
    "from itertools import chain\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        fbs = set(forbidden)\n",
    "        n=len(word)\n",
    "\n",
    "        dd={n:n} # right:left\n",
    "        for k in range(1, 11):\n",
    "            for i in range(n+1-k):\n",
    "                if word[i:i+k] in fbs:\n",
    "                    if i+k-1 not in dd:\n",
    "                        dd[i+k-1]=i\n",
    "                    else:\n",
    "                        dd[i+k-1]=max(dd[i+k-1], i)\n",
    "        a=sorted(dd.items())\n",
    "        # print(a)\n",
    "\n",
    "        ans = 0\n",
    "        pq = [1]\n",
    "        for ri, le in a:\n",
    "            # print(word[-pq[0]+1: ri])\n",
    "            length = ri+pq[0]-1  # word[-pq[0]+1: ri]\n",
    "            ans = max(ans, length)\n",
    "            # print(ans, le, ri, pq)\n",
    "            heappush(pq, -le)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        hashes = {}\n",
    "        for f in forbidden:\n",
    "            h, temp = 0, 1\n",
    "            for i in range(len(f) - 1, -1, -1):\n",
    "                h += temp * (ord(f[i]) - ord(\"a\"))\n",
    "                temp *= 26\n",
    "            if h not in hashes:\n",
    "                hashes[h] = set([len(f)])\n",
    "            else:\n",
    "                hashes[h].add(len(f))\n",
    "        window_hash = [0] * 10\n",
    "        left, max_len = 0, 0\n",
    "        for i in range(len(word)):\n",
    "            for j in range(9):\n",
    "                window_hash[j] = window_hash[j + 1] * 26\n",
    "            window_hash[9] = 0\n",
    "            for j in range(9, max(0, 9 - i) - 1, -1):\n",
    "                window_hash[j] += ord(word[i]) - ord(\"a\")\n",
    "                l = 10 - j\n",
    "                if window_hash[j] in hashes and l in hashes[window_hash[j]]:\n",
    "                    left = max(left, i - l + 2)\n",
    "                    break\n",
    "            max_len = max(max_len, i - left + 1)\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.tree = {}\n",
    "    def insert(self, word: str) -> None:\n",
    "        node = self.tree\n",
    "        for c in word:\n",
    "            if c not in node:\n",
    "                node[c] = {}\n",
    "            node = node[c]\n",
    "        node['end'] = True\n",
    "    def search(self, word: str) -> int:\n",
    "        node = self.tree\n",
    "        for i, c in enumerate(word):\n",
    "            if c not in node:\n",
    "                break\n",
    "            node = node[c]\n",
    "            if node.get('end'):\n",
    "                return i\n",
    "        return inf\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        trie = Trie()\n",
    "        for forb in forbidden:\n",
    "            trie.insert(forb)\n",
    "        \n",
    "        res = 0\n",
    "        N = len(word)\n",
    "        dp = 0\n",
    "        \n",
    "        for i in range(N - 1, -1, -1):\n",
    "            l = trie.search(word[i: i + 10])\n",
    "            dp = min(l, dp + 1)\n",
    "\n",
    "            res = max(res, dp)\n",
    "        \n",
    "        return res\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTree:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.tree = {}\n",
    "    \n",
    "    def add(self,word):\n",
    "        cur = self.tree\n",
    "        for w in word:\n",
    "            if w not in cur:\n",
    "                cur[w] = {}\n",
    "            cur = cur[w]\n",
    "        cur['end'] = True\n",
    "\n",
    "    def query(self,word):\n",
    "        cur = self.tree\n",
    "        for w in word:\n",
    "            if 'end' in cur:return True\n",
    "            if w not in cur:return False\n",
    "            cur = cur[w]\n",
    "        return 'end' in cur\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        tree =SegTree()\n",
    "        for w in forbidden:\n",
    "            tree.add(w)\n",
    "\n",
    "        def check(left,right):\n",
    "            left = max(right-10,left)\n",
    "            for i in range(left,right+1):\n",
    "                s = word[i:right+1]\n",
    "                if tree.query(s):return True\n",
    "            return False\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        for r , w in enumerate(word):\n",
    "            while check(l,r):\n",
    "                l += 1\n",
    "            ans = max(ans,r - l + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 给定k个单词和一段包含n个字符的文章,求有多少个单词在文章里`出现过`。\n",
    "# 若使用KMP算法,则每个模式串T,都要与主串S进行一次匹配,\n",
    "# !总时间复杂度为O(S1*k+S2),其中S1为主串S的长度,S2为`各个模式串的长度之和`,k为模式串的个数。\n",
    "# !而采用AC自动机,时间复杂度只需O(S1+S2)。\n",
    "# https://zhuanlan.zhihu.com/p/408665473\n",
    "# https://ikatakos.com/pot/programming_algorithm/string_search\n",
    "# AC自动机又叫AhoCorasick\n",
    "\n",
    "from typing import Generator, List, Tuple\n",
    "\n",
    "INF = int(2e18)\n",
    "\n",
    "\n",
    "class ACAutoMatonMap:\n",
    "    \"\"\"\n",
    "    不调用 BuildSuffixLink 就是Trie, 调用 BuildSuffixLink 就是AC自动机.\n",
    "    每个状态对应Trie中的一个结点, 也对应一个字符串.\n",
    "    \"\"\"\n",
    "\n",
    "    __slots__ = (\"wordPos\", \"_children\", \"_suffixLink\", \"_bfsOrder\")\n",
    "\n",
    "    def __init__(self):\n",
    "        self.wordPos = []\n",
    "        \"\"\"wordPos[i] 表示加入的第i个模式串对应的节点编号.\"\"\"\n",
    "        self._children = [{}]\n",
    "        \"\"\"_children[v][c] 表示节点v通过字符c转移到的节点.\"\"\"\n",
    "        self._suffixLink = []\n",
    "        \"\"\"又叫fail.指向当前节点最长真后缀对应结点,例如\"bc\"是\"abc\"的最长真后缀.\"\"\"\n",
    "        self._bfsOrder = []\n",
    "        \"\"\"结点的拓扑序,0表示虚拟节点.\"\"\"\n",
    "\n",
    "    def addString(self, string: str) -> int:\n",
    "        if not string:\n",
    "            return 0\n",
    "        pos = 0\n",
    "        for char in string:\n",
    "            nexts = self._children[pos]\n",
    "            if char in nexts:\n",
    "                pos = nexts[char]\n",
    "            else:\n",
    "                nextState = len(self._children)\n",
    "                nexts[char] = nextState\n",
    "                pos = nextState\n",
    "                self._children.append({})\n",
    "        self.wordPos.append(pos)\n",
    "        return pos\n",
    "\n",
    "    def addChar(self, pos: int, char: str) -> int:\n",
    "        nexts = self._children[pos]\n",
    "        if char in nexts:\n",
    "            return nexts[char]\n",
    "        nextState = len(self._children)\n",
    "        nexts[char] = nextState\n",
    "        self._children.append({})\n",
    "        return nextState\n",
    "\n",
    "    def move(self, pos: int, char: str) -> int:\n",
    "        children, link = self._children, self._suffixLink\n",
    "        while True:\n",
    "            nexts = children[pos]\n",
    "            if char in nexts:\n",
    "                return nexts[char]\n",
    "            if pos == 0:\n",
    "                return 0\n",
    "            pos = link[pos]\n",
    "\n",
    "    def buildSuffixLink(self):\n",
    "        \"\"\"\n",
    "        构建后缀链接(失配指针).\n",
    "        \"\"\"\n",
    "        self._suffixLink = [-1] * len(self._children)\n",
    "        self._bfsOrder = [0] * len(self._children)\n",
    "        head, tail = 0, 1\n",
    "        while head < tail:\n",
    "            v = self._bfsOrder[head]\n",
    "            head += 1\n",
    "            for char, next_ in self._children[v].items():\n",
    "                self._bfsOrder[tail] = next_\n",
    "                tail += 1\n",
    "                f = self._suffixLink[v]\n",
    "                while f != -1 and char not in self._children[f]:\n",
    "                    f = self._suffixLink[f]\n",
    "\n",
    "                if f == -1:\n",
    "                    self._suffixLink[next_] = 0\n",
    "                else:\n",
    "                    self._suffixLink[next_] = self._children[f][char]\n",
    "\n",
    "    def getCounter(self) -> List[int]:\n",
    "        \"\"\"获取每个状态匹配到的模式串的个数.\"\"\"\n",
    "        counter = [0] * len(self._children)\n",
    "        for pos in self.wordPos:\n",
    "            counter[pos] += 1\n",
    "        for v in self._bfsOrder:\n",
    "            if v != 0:\n",
    "                counter[v] += counter[self._suffixLink[v]]\n",
    "        return counter\n",
    "\n",
    "    def getIndexes(self) -> List[List[int]]:\n",
    "        \"\"\"获取每个状态匹配到的模式串的索引.\"\"\"\n",
    "        res = [[] for _ in range(len(self._children))]\n",
    "        for i, pos in enumerate(self.wordPos):\n",
    "            res[pos].append(i)\n",
    "        for v in self._bfsOrder:\n",
    "            if v != 0:\n",
    "                from_, _children = self._suffixLink[v], v\n",
    "                arr1, arr2 = res[from_], res[_children]\n",
    "                arr3 = [0] * (len(arr1) + len(arr2))\n",
    "                i, j, k = 0, 0, 0\n",
    "                while i < len(arr1) and j < len(arr2):\n",
    "                    if arr1[i] < arr2[j]:\n",
    "                        arr3[k] = arr1[i]\n",
    "                        i += 1\n",
    "                    elif arr1[i] > arr2[j]:\n",
    "                        arr3[k] = arr2[j]\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        arr3[k] = arr1[i]\n",
    "                        i += 1\n",
    "                        j += 1\n",
    "                    k += 1\n",
    "                while i < len(arr1):\n",
    "                    arr3[k] = arr1[i]\n",
    "                    i += 1\n",
    "                    k += 1\n",
    "                while j < len(arr2):\n",
    "                    arr3[k] = arr2[j]\n",
    "                    j += 1\n",
    "                    k += 1\n",
    "                res[_children] = arr3\n",
    "        return res\n",
    "\n",
    "    def dp(self) -> Generator[Tuple[int, int], None, None]:\n",
    "        for v in self._bfsOrder:\n",
    "            if v != 0:\n",
    "                yield self._suffixLink[v], v\n",
    "\n",
    "    @property\n",
    "    def size(self) -> int:\n",
    "        return len(self._children)\n",
    "\n",
    "    def __len__(self) -> int:\n",
    "        return len(self._children)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # 1032. 字符流\n",
    "    # https://leetcode.cn/problems/stream-of-characters/description/\n",
    "    class StreamChecker:\n",
    "        __slots__ = (\"ac\", \"counter\", \"pos\")\n",
    "\n",
    "        def __init__(self, wordPos: List[str]):\n",
    "            self.ac = ACAutoMatonMap()\n",
    "            for word in wordPos:\n",
    "                self.ac.addString(word)\n",
    "            self.ac.buildSuffixLink()\n",
    "            self.counter = self.ac.getCounter()\n",
    "            self.pos = 0\n",
    "\n",
    "        def query(self, letter: str) -> bool:\n",
    "            self.pos = self.ac.move(self.pos, letter)\n",
    "            return self.counter[self.pos] > 0\n",
    "\n",
    "    # https://leetcode.cn/problems/multi-search-lcci/\n",
    "    # 给定一个较长字符串big和一个包含较短字符串的数组smalls，\n",
    "    # 设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。\n",
    "    # !输出smalls中的字符串在big里出现的所有位置positions，\n",
    "    # 其中positions[i]为smalls[i]出现的所有位置。\n",
    "    class Solution1:\n",
    "        def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "            acm = ACAutoMatonMap()\n",
    "            for s in smalls:\n",
    "                acm.addString(s)\n",
    "            acm.buildSuffixLink()\n",
    "\n",
    "            indexes = acm.getIndexes()\n",
    "            res = [[] for _ in range(len(smalls))]\n",
    "            pos = 0\n",
    "            for i, char in enumerate(big):\n",
    "                pos = acm.move(pos, char)\n",
    "                for index in indexes[pos]:\n",
    "                    res[index].append(i - len(smalls[index]) + 1)\n",
    "            return res\n",
    "\n",
    "    # 2781. 最长合法子字符串的长度\n",
    "    # https://leetcode.cn/problems/length-of-the-longest-valid-substring/\n",
    "    # 给你一个字符串 word 和一个字符串数组 forbidden 。\n",
    "    # 如果一个字符串不包含 forbidden 中的任何字符串，我们称这个字符串是 合法 的。\n",
    "    # 请你返回字符串 word 的一个 最长合法子字符串 的长度。\n",
    "    # 子字符串 指的是一个字符串中一段连续的字符，它可以为空。\n",
    "    #\n",
    "    # 1 <= word.length <= 1e5\n",
    "    # word 只包含小写英文字母。\n",
    "    # 1 <= forbidden.length <= 1e5\n",
    "    # !1 <= forbidden[i].length <= 1e5\n",
    "    # !sum(len(forbidden)) <= 1e7\n",
    "    # forbidden[i] 只包含小写英文字母。\n",
    "    #\n",
    "    # 思路:\n",
    "    # 类似字符流, 需要处理出每个位置为结束字符的包含至少一个模式串的`最短后缀`.\n",
    "    # !那么此时左端点就对应这个位置+1\n",
    "    class Solution:\n",
    "        def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "            def min(a: int, b: int) -> int:\n",
    "                return a if a < b else b\n",
    "\n",
    "            def max(a: int, b: int) -> int:\n",
    "                return a if a > b else b\n",
    "\n",
    "            acm = ACAutoMatonMap()\n",
    "            for s in forbidden:\n",
    "                acm.addString(s)\n",
    "            acm.buildSuffixLink()\n",
    "\n",
    "            minLen = [INF] * len(acm)\n",
    "            for i, pos in enumerate(acm.wordPos):\n",
    "                minLen[pos] = min(minLen[pos], len(forbidden[i]))\n",
    "            for pre, cur in acm.dp():\n",
    "                minLen[cur] = min(minLen[cur], minLen[pre])\n",
    "\n",
    "            res, left, pos = 0, 0, 0\n",
    "            for right, char in enumerate(word):\n",
    "                pos = acm.move(pos, char)\n",
    "                left = max(left, right - minLen[pos] + 2)\n",
    "                res = max(res, right - left + 1)\n",
    "\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Dict, Generator, List, Tuple, Union\n",
    "\n",
    "INF = int(2e18)\n",
    "\n",
    "\n",
    "class ACAutoMatonMap:\n",
    "    \"\"\"\n",
    "    不调用 BuildSuffixLink 就是Trie,调用 BuildSuffixLink 就是AC自动机.\n",
    "    每个状态对应Trie中的一个结点,也对应一个字符串.\n",
    "    \"\"\"\n",
    "\n",
    "    __slots__ = (\n",
    "        \"to\",\n",
    "        \"words\",\n",
    "        \"bfsOrder\",\n",
    "        \"_suffixLink\",\n",
    "    )\n",
    "\n",
    "    def __init__(self):\n",
    "        self.to: List[Dict[str, int]] = [{}]\n",
    "        \"\"\"to[v][c] 表示节点v通过字符c转移到的节点.\"\"\"\n",
    "        self.words = []\n",
    "        \"\"\"words[i] 表示加入的第i个模式串对应的节点编号.\"\"\"\n",
    "        self.bfsOrder = []\n",
    "        \"\"\"结点的拓扑序,0表示虚拟节点.\"\"\"\n",
    "        self._suffixLink = []\n",
    "        \"\"\"又叫fail.指向当前节点最长真后缀对应结点,例如\"bc\"是\"abc\"的最长真后缀.\"\"\"\n",
    "\n",
    "    def addString(self, string: str) -> int:\n",
    "        if not string:\n",
    "            return 0\n",
    "        pos = 0\n",
    "        for char in string:\n",
    "            nexts = self.to[pos]\n",
    "            if char in nexts:\n",
    "                pos = nexts[char]\n",
    "            else:\n",
    "                nextState = len(self.to)\n",
    "                nexts[char] = nextState\n",
    "                pos = nextState\n",
    "                self.to.append({})\n",
    "        self.words.append(pos)\n",
    "        return pos\n",
    "\n",
    "    def addChar(self, pos: int, char: str) -> int:\n",
    "        nexts = self.to[pos]\n",
    "        if char in nexts:\n",
    "            return nexts[char]\n",
    "        nextState = len(self.to)\n",
    "        nexts[char] = nextState\n",
    "        self.to.append({})\n",
    "        return nextState\n",
    "\n",
    "    def move(self, pos: int, char: str) -> int:\n",
    "        to, fail = self.to, self._suffixLink\n",
    "        while True:\n",
    "            nexts = to[pos]\n",
    "            if char in nexts:\n",
    "                return nexts[char]\n",
    "            if pos == 0:\n",
    "                return 0\n",
    "            pos = fail[pos]\n",
    "\n",
    "    def buildSuffixLink(self):\n",
    "        \"\"\"\n",
    "        构建后缀链接(失配指针).\n",
    "        \"\"\"\n",
    "        self._suffixLink = [-1] * len(self.to)\n",
    "        self.bfsOrder = [0] * len(self.to)\n",
    "        head, tail = 0, 1\n",
    "        while head < tail:\n",
    "            v = self.bfsOrder[head]\n",
    "            head += 1\n",
    "            for char, next_ in self.to[v].items():\n",
    "                self.bfsOrder[tail] = next_\n",
    "                tail += 1\n",
    "                f = self._suffixLink[v]\n",
    "                while f != -1 and char not in self.to[f]:\n",
    "                    f = self._suffixLink[f]\n",
    "                self._suffixLink[next_] = f\n",
    "                if f == -1:\n",
    "                    self._suffixLink[next_] = 0\n",
    "                else:\n",
    "                    self._suffixLink[next_] = self.to[f][char]\n",
    "\n",
    "    def getCounter(self) -> List[int]:\n",
    "        \"\"\"获取每个状态匹配到的模式串的个数.\"\"\"\n",
    "        counter = [0] * len(self.to)\n",
    "        for pos in self.words:\n",
    "            counter[pos] += 1\n",
    "        for v in self.bfsOrder:\n",
    "            if v != 0:\n",
    "                counter[v] += counter[self._suffixLink[v]]\n",
    "        return counter\n",
    "\n",
    "    def getIndexes(self) -> List[List[int]]:\n",
    "        \"\"\"获取每个状态匹配到的模式串的索引.\"\"\"\n",
    "        res = [[] for _ in range(len(self.to))]\n",
    "        for i, pos in enumerate(self.words):\n",
    "            res[pos].append(i)\n",
    "        for v in self.bfsOrder:\n",
    "            if v != 0:\n",
    "                from_, to = self._suffixLink[v], v\n",
    "                arr1, arr2 = res[from_], res[to]\n",
    "                arr3 = [0] * (len(arr1) + len(arr2))\n",
    "                i, j, k = 0, 0, 0\n",
    "                while i < len(arr1) and j < len(arr2):\n",
    "                    if arr1[i] < arr2[j]:\n",
    "                        arr3[k] = arr1[i]\n",
    "                        i += 1\n",
    "                    elif arr1[i] > arr2[j]:\n",
    "                        arr3[k] = arr2[j]\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        arr3[k] = arr1[i]\n",
    "                        i += 1\n",
    "                        j += 1\n",
    "                    k += 1\n",
    "                while i < len(arr1):\n",
    "                    arr3[k] = arr1[i]\n",
    "                    i += 1\n",
    "                    k += 1\n",
    "                while j < len(arr2):\n",
    "                    arr3[k] = arr2[j]\n",
    "                    j += 1\n",
    "                    k += 1\n",
    "                res[to] = arr3\n",
    "        return res\n",
    "\n",
    "    def dp(self) -> Generator[Tuple[int, int], None, None]:\n",
    "        for v in self.bfsOrder:\n",
    "            if v != 0:\n",
    "                yield self._suffixLink[v], v\n",
    "\n",
    "    @property\n",
    "    def size(self) -> int:\n",
    "        return len(self.to)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # 1032. 字符流\n",
    "    # https://leetcode.cn/problems/stream-of-characters/description/\n",
    "    class StreamChecker:\n",
    "        __slots__ = (\"ac\", \"counter\", \"pos\")\n",
    "\n",
    "        def __init__(self, words: List[str]):\n",
    "            self.ac = ACAutoMatonMap()\n",
    "            for word in words:\n",
    "                self.ac.addString(word)\n",
    "            self.ac.buildSuffixLink()\n",
    "            self.counter = self.ac.getCounter()\n",
    "            self.pos = 0\n",
    "\n",
    "        def query(self, letter: str) -> bool:\n",
    "            self.pos = self.ac.move(self.pos, letter)\n",
    "            return self.counter[self.pos] > 0\n",
    "\n",
    "    # https://leetcode.cn/problems/multi-search-lcci/\n",
    "    # 给定一个较长字符串big和一个包含较短字符串的数组smalls，\n",
    "    # 设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。\n",
    "    # !输出smalls中的字符串在big里出现的所有位置positions，\n",
    "    # 其中positions[i]为smalls[i]出现的所有位置。\n",
    "    class Solution1:\n",
    "        def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "            acm = ACAutoMatonMap()\n",
    "            for s in smalls:\n",
    "                acm.addString(s)\n",
    "            acm.buildSuffixLink()\n",
    "\n",
    "            indexes = acm.getIndexes()\n",
    "            res = [[] for _ in range(len(smalls))]\n",
    "            pos = 0\n",
    "            for i, char in enumerate(big):\n",
    "                pos = acm.move(pos, char)\n",
    "                for index in indexes[pos]:\n",
    "                    res[index].append(i - len(smalls[index]) + 1)\n",
    "            return res\n",
    "\n",
    "    # 2781. 最长合法子字符串的长度\n",
    "    # https://leetcode.cn/problems/length-of-the-longest-valid-substring/\n",
    "    # 给你一个字符串 word 和一个字符串数组 forbidden 。\n",
    "    # 如果一个字符串不包含 forbidden 中的任何字符串，我们称这个字符串是 合法 的。\n",
    "    # 请你返回字符串 word 的一个 最长合法子字符串 的长度。\n",
    "    # 子字符串 指的是一个字符串中一段连续的字符，它可以为空。\n",
    "    #\n",
    "    # 1 <= word.length <= 1e5\n",
    "    # word 只包含小写英文字母。\n",
    "    # 1 <= forbidden.length <= 1e5\n",
    "    # !1 <= forbidden[i].length <= 1e5\n",
    "    # !sum(len(forbidden)) <= 1e7\n",
    "    # forbidden[i] 只包含小写英文字母。\n",
    "    #\n",
    "    # 思路:\n",
    "    # 类似字符流, 需要处理出每个位置为结束字符的包含至少一个模式串的`最短后缀`.\n",
    "    # !那么此时左端点就对应这个位置+1\n",
    "    class Solution:\n",
    "        def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "            def min(a: int, b: int) -> int:\n",
    "                return a if a < b else b\n",
    "\n",
    "            def max(a: int, b: int) -> int:\n",
    "                return a if a > b else b\n",
    "\n",
    "            acm = ACAutoMatonMap()\n",
    "            for s in forbidden:\n",
    "                acm.addString(s)\n",
    "            acm.buildSuffixLink()\n",
    "\n",
    "            minLen = [INF] * acm.size\n",
    "            for i, pos in enumerate(acm.words):\n",
    "                minLen[pos] = min(minLen[pos], len(forbidden[i]))\n",
    "            for pre, cur in acm.dp():\n",
    "                minLen[cur] = min(minLen[cur], minLen[pre])\n",
    "\n",
    "            res, left, pos = 0, 0, 0\n",
    "            for right, char in enumerate(word):\n",
    "                pos = acm.move(pos, char)\n",
    "                left = max(left, right - minLen[pos] + 2)\n",
    "                res = max(res, right - left + 1)\n",
    "\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 给定k个单词和一段包含n个字符的文章,求有多少个单词在文章里`出现过`。\n",
    "# 若使用KMP算法,则每个模式串T,都要与主串S进行一次匹配,\n",
    "# !总时间复杂度为O(S1*k+S2),其中S1为主串S的长度,S2为`各个模式串的长度之和`,k为模式串的个数。\n",
    "# !而采用AC自动机,时间复杂度只需O(S1+S2)。\n",
    "# https://zhuanlan.zhihu.com/p/408665473\n",
    "# https://ikatakos.com/pot/programming_algorithm/string_search\n",
    "# AC自动机又叫AhoCorasick\n",
    "\n",
    "from typing import Generator, List, Tuple\n",
    "\n",
    "INF = int(2e18)\n",
    "\n",
    "\n",
    "class ACAutoMatonMap:\n",
    "    \"\"\"\n",
    "    不调用 BuildSuffixLink 就是Trie, 调用 BuildSuffixLink 就是AC自动机.\n",
    "    每个状态对应Trie中的一个结点, 也对应一个字符串.\n",
    "    \"\"\"\n",
    "\n",
    "    __slots__ = (\"wordPos\", \"_children\", \"_suffixLink\", \"_bfsOrder\")\n",
    "\n",
    "    def __init__(self):\n",
    "        self.wordPos = []\n",
    "        \"\"\"wordPos[i] 表示加入的第i个模式串对应的节点编号.\"\"\"\n",
    "        self._children = [{}]\n",
    "        \"\"\"_children[v][c] 表示节点v通过字符c转移到的节点.\"\"\"\n",
    "        self._suffixLink = []\n",
    "        \"\"\"又叫fail.指向当前节点最长真后缀对应结点,例如\"bc\"是\"abc\"的最长真后缀.\"\"\"\n",
    "        self._bfsOrder = []\n",
    "        \"\"\"结点的拓扑序,0表示虚拟节点.\"\"\"\n",
    "\n",
    "    def addString(self, string: str) -> int:\n",
    "        if not string:\n",
    "            return 0\n",
    "        pos = 0\n",
    "        for char in string:\n",
    "            nexts = self._children[pos]\n",
    "            if char in nexts:\n",
    "                pos = nexts[char]\n",
    "            else:\n",
    "                nextState = len(self._children)\n",
    "                nexts[char] = nextState\n",
    "                pos = nextState\n",
    "                self._children.append({})\n",
    "        self.wordPos.append(pos)\n",
    "        return pos\n",
    "\n",
    "    def addChar(self, pos: int, char: str) -> int:\n",
    "        nexts = self._children[pos]\n",
    "        if char in nexts:\n",
    "            return nexts[char]\n",
    "        nextState = len(self._children)\n",
    "        nexts[char] = nextState\n",
    "        self._children.append({})\n",
    "        return nextState\n",
    "\n",
    "    def move(self, pos: int, char: str) -> int:\n",
    "        children, link = self._children, self._suffixLink\n",
    "        while True:\n",
    "            nexts = children[pos]\n",
    "            if char in nexts:\n",
    "                return nexts[char]\n",
    "            if pos == 0:\n",
    "                return 0\n",
    "            pos = link[pos]\n",
    "\n",
    "    def buildSuffixLink(self):\n",
    "        \"\"\"\n",
    "        构建后缀链接(失配指针).\n",
    "        \"\"\"\n",
    "        self._suffixLink = [-1] * len(self._children)\n",
    "        self._bfsOrder = [0] * len(self._children)\n",
    "        head, tail = 0, 1\n",
    "        while head < tail:\n",
    "            v = self._bfsOrder[head]\n",
    "            head += 1\n",
    "            for char, next_ in self._children[v].items():\n",
    "                self._bfsOrder[tail] = next_\n",
    "                tail += 1\n",
    "                f = self._suffixLink[v]\n",
    "                while f != -1 and char not in self._children[f]:\n",
    "                    f = self._suffixLink[f]\n",
    "                self._suffixLink[next_] = f\n",
    "                if f == -1:\n",
    "                    self._suffixLink[next_] = 0\n",
    "                else:\n",
    "                    self._suffixLink[next_] = self._children[f][char]\n",
    "\n",
    "    def getCounter(self) -> List[int]:\n",
    "        \"\"\"获取每个状态匹配到的模式串的个数.\"\"\"\n",
    "        counter = [0] * len(self._children)\n",
    "        for pos in self.wordPos:\n",
    "            counter[pos] += 1\n",
    "        for v in self._bfsOrder:\n",
    "            if v != 0:\n",
    "                counter[v] += counter[self._suffixLink[v]]\n",
    "        return counter\n",
    "\n",
    "    def getIndexes(self) -> List[List[int]]:\n",
    "        \"\"\"获取每个状态匹配到的模式串的索引.\"\"\"\n",
    "        res = [[] for _ in range(len(self._children))]\n",
    "        for i, pos in enumerate(self.wordPos):\n",
    "            res[pos].append(i)\n",
    "        for v in self._bfsOrder:\n",
    "            if v != 0:\n",
    "                from_, _children = self._suffixLink[v], v\n",
    "                arr1, arr2 = res[from_], res[_children]\n",
    "                arr3 = [0] * (len(arr1) + len(arr2))\n",
    "                i, j, k = 0, 0, 0\n",
    "                while i < len(arr1) and j < len(arr2):\n",
    "                    if arr1[i] < arr2[j]:\n",
    "                        arr3[k] = arr1[i]\n",
    "                        i += 1\n",
    "                    elif arr1[i] > arr2[j]:\n",
    "                        arr3[k] = arr2[j]\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        arr3[k] = arr1[i]\n",
    "                        i += 1\n",
    "                        j += 1\n",
    "                    k += 1\n",
    "                while i < len(arr1):\n",
    "                    arr3[k] = arr1[i]\n",
    "                    i += 1\n",
    "                    k += 1\n",
    "                while j < len(arr2):\n",
    "                    arr3[k] = arr2[j]\n",
    "                    j += 1\n",
    "                    k += 1\n",
    "                res[_children] = arr3\n",
    "        return res\n",
    "\n",
    "    def dp(self) -> Generator[Tuple[int, int], None, None]:\n",
    "        for v in self._bfsOrder:\n",
    "            if v != 0:\n",
    "                yield self._suffixLink[v], v\n",
    "\n",
    "    @property\n",
    "    def size(self) -> int:\n",
    "        return len(self._children)\n",
    "\n",
    "    def __len__(self) -> int:\n",
    "        return len(self._children)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # 1032. 字符流\n",
    "    # https://leetcode.cn/problems/stream-of-characters/description/\n",
    "    class StreamChecker:\n",
    "        __slots__ = (\"ac\", \"counter\", \"pos\")\n",
    "\n",
    "        def __init__(self, wordPos: List[str]):\n",
    "            self.ac = ACAutoMatonMap()\n",
    "            for word in wordPos:\n",
    "                self.ac.addString(word)\n",
    "            self.ac.buildSuffixLink()\n",
    "            self.counter = self.ac.getCounter()\n",
    "            self.pos = 0\n",
    "\n",
    "        def query(self, letter: str) -> bool:\n",
    "            self.pos = self.ac.move(self.pos, letter)\n",
    "            return self.counter[self.pos] > 0\n",
    "\n",
    "    # https://leetcode.cn/problems/multi-search-lcci/\n",
    "    # 给定一个较长字符串big和一个包含较短字符串的数组smalls，\n",
    "    # 设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。\n",
    "    # !输出smalls中的字符串在big里出现的所有位置positions，\n",
    "    # 其中positions[i]为smalls[i]出现的所有位置。\n",
    "    class Solution1:\n",
    "        def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:\n",
    "            acm = ACAutoMatonMap()\n",
    "            for s in smalls:\n",
    "                acm.addString(s)\n",
    "            acm.buildSuffixLink()\n",
    "\n",
    "            indexes = acm.getIndexes()\n",
    "            res = [[] for _ in range(len(smalls))]\n",
    "            pos = 0\n",
    "            for i, char in enumerate(big):\n",
    "                pos = acm.move(pos, char)\n",
    "                for index in indexes[pos]:\n",
    "                    res[index].append(i - len(smalls[index]) + 1)\n",
    "            return res\n",
    "\n",
    "    # 2781. 最长合法子字符串的长度\n",
    "    # https://leetcode.cn/problems/length-of-the-longest-valid-substring/\n",
    "    # 给你一个字符串 word 和一个字符串数组 forbidden 。\n",
    "    # 如果一个字符串不包含 forbidden 中的任何字符串，我们称这个字符串是 合法 的。\n",
    "    # 请你返回字符串 word 的一个 最长合法子字符串 的长度。\n",
    "    # 子字符串 指的是一个字符串中一段连续的字符，它可以为空。\n",
    "    #\n",
    "    # 1 <= word.length <= 1e5\n",
    "    # word 只包含小写英文字母。\n",
    "    # 1 <= forbidden.length <= 1e5\n",
    "    # !1 <= forbidden[i].length <= 1e5\n",
    "    # !sum(len(forbidden)) <= 1e7\n",
    "    # forbidden[i] 只包含小写英文字母。\n",
    "    #\n",
    "    # 思路:\n",
    "    # 类似字符流, 需要处理出每个位置为结束字符的包含至少一个模式串的`最短后缀`.\n",
    "    # !那么此时左端点就对应这个位置+1\n",
    "    class Solution:\n",
    "        def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "            def min(a: int, b: int) -> int:\n",
    "                return a if a < b else b\n",
    "\n",
    "            def max(a: int, b: int) -> int:\n",
    "                return a if a > b else b\n",
    "\n",
    "            acm = ACAutoMatonMap()\n",
    "            for s in forbidden:\n",
    "                acm.addString(s)\n",
    "            acm.buildSuffixLink()\n",
    "\n",
    "            minLen = [INF] * len(acm)\n",
    "            for i, pos in enumerate(acm.wordPos):\n",
    "                minLen[pos] = len(forbidden[i])\n",
    "            for pre, cur in acm.dp():\n",
    "                minLen[cur] = min(minLen[cur], minLen[pre])\n",
    "\n",
    "            res, left, pos = 0, 0, 0\n",
    "            for right, char in enumerate(word):\n",
    "                pos = acm.move(pos, char)\n",
    "                left = max(left, right - minLen[pos] + 2)\n",
    "                res = max(res, right - left + 1)\n",
    "\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        def dicCreate(l):\n",
    "            dic = [False, {}]\n",
    "            for x in l:\n",
    "                pres = dic\n",
    "                for y in x:\n",
    "                    if y not in pres[1]:\n",
    "                        pres[1][y] = [0, {}]\n",
    "                    pres = pres[1][y]\n",
    "                pres[0] = True\n",
    "            return dic\n",
    "        \n",
    "        dic, stack = dicCreate(forbidden), []\n",
    "        for i in range(len(word)):\n",
    "            pres = dic\n",
    "            for j in range(i, min(i + 10, len(word))):\n",
    "                if word[j] not in pres[1]:\n",
    "                    break\n",
    "                pres = pres[1][word[j]]\n",
    "                if pres[0]:\n",
    "                    while stack and stack[-1][1] >= j:\n",
    "                        stack.pop()\n",
    "                    stack.append([i, j])\n",
    "                    break\n",
    "        return max(stack[0][1], len(word) - stack[-1][0] - 1, max(stack[i + 1][1] - stack[i][0] - 1 for i in range(len(stack) - 1)) if len(stack) > 1 else -1) if stack else len(word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    __slots__ = [\"children\", \"ended\"]\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.ended = False\n",
    "\n",
    "    def insert(self, word):\n",
    "        crt = self\n",
    "        for c in word:\n",
    "            code = ord(c) - ord(\"a\")\n",
    "            if crt.children[code] is None: \n",
    "                crt.children[code] = Trie()\n",
    "            crt = crt.children[code]\n",
    "        crt.ended = True\n",
    "\n",
    "    def find(self, word):\n",
    "        #print(\"searching\", word)\n",
    "        crt = self\n",
    "        ans = 0\n",
    "        for c in word:\n",
    "            code = ord(c) - ord(\"a\")  \n",
    "            crt = crt.children[code]\n",
    "            if crt:\n",
    "                ans += 1\n",
    "                if crt.ended:\n",
    "                    return ans\n",
    "            else:\n",
    "                return -1\n",
    "        return -1\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        ans = left = 0\n",
    "        #fb_set = set(forbidden)\n",
    "        tree = Trie()\n",
    "        for fbn in forbidden:\n",
    "            tree.insert(reversed(fbn))\n",
    "        for right in range(len(word)):\n",
    "            # for j in range(right, max(left - 1, right - 10), -1):\n",
    "            #     if word[j:right + 1] in fb_set:\n",
    "            to_search_word = word[max(0, left - 1, right - 10):(right + 1)]\n",
    "            if (j := tree.find(to_search_word[::-1])) >= 0:\n",
    "                #print(right, j)\n",
    "                left = right - j + 2\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.finish = False\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        trie = Trie()\n",
    "        for f in forbidden:\n",
    "            cur = trie\n",
    "            for c in f:\n",
    "                if c not in cur.children:\n",
    "                    cur.children[c] = Trie()\n",
    "                cur = cur.children[c]\n",
    "            cur.finish = True\n",
    "\n",
    "        n = len(word)\n",
    "        ans = 0\n",
    "        r = n\n",
    "\n",
    "        for l in range(n-1,-1,-1):\n",
    "            cur = trie\n",
    "            for j in range(l,r):\n",
    "                if word[j] in cur.children:\n",
    "                    cur = cur.children[word[j]]\n",
    "                    if cur.finish:\n",
    "                        r = j\n",
    "                        break \n",
    "                else:\n",
    "                    break \n",
    "            ans = max(ans, r-l)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.is_word = False \n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        n = len(word)\n",
    "        root = TrieNode()\n",
    "        for w in forbidden:\n",
    "            node = root\n",
    "            for c in w:\n",
    "                if c not in node.children:\n",
    "                    node.children[c] = TrieNode()\n",
    "                node = node.children[c]\n",
    "            node.is_word = True \n",
    "        l = 0\n",
    "        res = 0\n",
    "        for r in range(n):\n",
    "            for start in range(r, max(l - 1, r - 10), - 1):\n",
    "                node = root \n",
    "                for i in range(start, r + 1):\n",
    "                    if word[i] not in node.children:\n",
    "                        break \n",
    "                    node = node.children[word[i]]\n",
    "                    if node.is_word:\n",
    "                        l = start + 1 \n",
    "                        break\n",
    "            res = max(res, r - l + 1)\n",
    "        return res \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.is_word = False\n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        n = len(word)\n",
    "        root = TrieNode()\n",
    "        for w in forbidden:\n",
    "            node = root \n",
    "            for c in w:\n",
    "                if c not in node.children:\n",
    "                    node.children[c] = TrieNode()\n",
    "                node = node.children[c]\n",
    "            node.is_word = True \n",
    "        l = 0\n",
    "        res = 0\n",
    "        for r in range(n):\n",
    "            for start in range(r, max(l - 1, r - 10), - 1):\n",
    "                node = root  \n",
    "                for i in range(start, r + 1):\n",
    "                    if word[i] not in node.children:\n",
    "                        break  \n",
    "                    node = node.children[word[i]]\n",
    "                    if node.is_word:\n",
    "                        l = start + 1 \n",
    "                        break\n",
    "            res = max(res, r - l + 1)\n",
    "        return res \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.is_word = False \n",
    "\n",
    "class Solution:\n",
    "    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:\n",
    "        root = TrieNode()\n",
    "        for w in forbidden:\n",
    "            node = root \n",
    "            for c in w:\n",
    "                if c not in node.children:\n",
    "                    node.children[c] = TrieNode()\n",
    "                node = node.children[c]\n",
    "            node.is_word = True \n",
    "        n = len(word)\n",
    "        res = 0\n",
    "        l = 0\n",
    "        for r in range(n):\n",
    "            for start in range(r, max(l - 1, r - 10), - 1):\n",
    "                node = root \n",
    "                for idx in range(start, r + 1):\n",
    "                    if word[idx] not in node.children:\n",
    "                        break \n",
    "                    node = node.children[word[idx]]\n",
    "                    if node.is_word:\n",
    "                        l = start + 1 \n",
    "                        break \n",
    "            res = max(res, r - l + 1)\n",
    "        return res \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
